排列数字
题目 排列数字
思路分析
最暴力的写法
枚举每一位可放的数 有几位就得写几重循环
#include<bits/stdc++.h>
using namespace std;
#define lf else if
int main(){
int n;
cin>>n;
if(n==1){cout<<"1";}
if(n==2)cout<<"1 2\n2 1";
if(n==3)cout<<"1 2 3\n1 3 2\n2 1 3\n2 3 1\n3 1 2\n3 2 1";
if(n==4){
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++){
for(int k = 1;k<=n;k++){
for(int l = 1;l<=n;l++){
if(i+j+k+l==10&&i*k*j*l==24)printf("%d %d %d %d\n",i,j,k,l);
}
}
}
}
}
if(n==5){
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++){
for(int k = 1;k<=n;k++){
for(int l = 1;l<=n;l++){
for(int a = 1;a<=n;a++){
if(i+j+k+l+a==15&&i*k*j*l*a==120)printf("%d %d %d %d %d\n",i,j,k,l,a);
}
}
}
}
}
}
if(n==6){
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++){
for(int k = 1;k<=n;k++){
for(int l = 1;l<=n;l++){
for(int a = 1;a<=n;a++){
for(int b = 1;b<=n;b++){
if(i+j+k+l+a+b==21&&i*k*j*l*a*b==720)printf("%d %d %d %d %d %d\n",i,j,k,l,a,b);
}
}
}
}
}
}
}
else{
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++){
for(int k = 1;k<=n;k++){
for(int l = 1;l<=n;l++){
for(int a = 1;a<=n;a++){
for(int b = 1;b<=n;b++){
for(int c = 1;c<=n;c++)if(i+j+k+l+a+b+c==28&&i*k*j*l*a*b*c==5040)printf("%d %d %d %d %d %d %d\n",i,j,k,l,a,b,c);
}
}
}
}
}
}
}
return 0;
}
但发现其实有些性质 前一位放了某个数 后一位能放的数就受到了限制
其实可以按每一位来处理
首先看第一位能有哪些种情况 第一位确定后 再看第二位可以放哪些 以此类推 若推到最后达到n位了 就说明这种情况成立了
可以抽象成一棵递归搜索树
#include<bits/stdc++.h>
using namespace std;
const int N=10;
int path[N];
bool st[N];
int n;
void dfs(int u,int n){
if(u==n){
for(int i=0;i<n;i++)
cout<<path[i]<<" ";
cout<<endl;
return;
}
for(int i=1;i<=n;i++){
if(!st[i]){
st[i]=true;
path[u]=i;
dfs(u+1,n);
path[u]=0;
st[i]=false;
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
dfs(0,n);
return 0;
}
用path数组记录每一位（u代表当前位） 用st数组记录某个数是否在前面已经被用过 然后从第0层开始递归 首先看的是第0位（第一位）能放什么 在1~n里面选 如果某个数没被用过 就可以选这个数 再看第0位确定了这个数之后有哪些选法 要把这个数标记选过了 且 进入u+1层继续看能选哪些数……
这类问题有个库函数 next_permutation 可以解决
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;cin>>n;
vector<int> all;
for(int i=1;i<=n;i++)
all.push_back(i);
do{
for(int num:all)
cout<<num<<" ";
cout<<endl;
}while(next_permutation(all.begin(),all.end()));
return 0;
}
代码实现
💬 评论